package DailyPractice.Day19;

import java.util.Scanner;

/**
 * 最长公共子字符串
 *
 * @author lumin
 * @date 2022/05/15 20:27
 **/
public class Num2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        String str = longStr(str1, str2);
        System.out.println(str);
    }

    private static String longStr(String str1, String str2) {
        if (str1.length() == 0 || str2.length() == 0) {
            return "";
        }
        if (str1.length() > str2.length()) {
            return longStr(str2, str1);
        }
        int m = str1.length(), n = str2.length();
        //使用dp[i][j]表示以i,j结尾的最长公共子串长度
        //dp[i][j] = dp[i-1][j-1] + 1;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (str1.charAt(i) == str2.charAt(0)) {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (str1.charAt(0) == str2.charAt(i)) {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        int maxLength = 0;
        int endIndex = 0; //从str1上取的end，也就是表示优先取str1上第一次出现的
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    endIndex = i;
                }
            }
        }
        return str1.substring(endIndex - maxLength + 1, endIndex + 1);
    }
}